/*
 * @Author: your name
 * @Date: 2024-05-16 12:33:47
 * @LastEditTime: 2024-05-16 13:03:13
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\37.解数独.cpp
 */
/*
 * @lc app=leetcode.cn id=37 lang=cpp
 *
 * [37] 解数独
 */

// @lc code=start
class Solution {
public:
    bool isValid(int row, int col, char ch, vector<vector<char>>& board){
        // 行
        for(int i = 0; i < board[0].size(); i++){
            if(ch == board[row][i]){
                return false;
            }
        }
        // 列
        for(int i = 0; i < board.size(); i++){
            if(ch == board[i][col]){
                return false;
            }
        }
        // 小区域内
        int start_row = (row/3)*3;
        int start_col = (col/3)*3;
        for(int i = start_row; i <start_row + 3; i++ ){
            for (int j = start_col; j < start_col+3; j++){
                if(ch == board[i][j]){
                    return false;
                }
            }
            
        }
        return true;
    }
    bool backtracking(vector<vector<char>>& board){
        // 不用终止条件
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                if(board[i][j] != '.') continue;
                for(char k = '1'; k <= '9'; k++){
                    if(isValid(i,j,k,board)){
                        board[i][j] = k;
                        if(backtracking(board)){
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                return false;
            }   
            
        }
        return true;
        
    }
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
       
    }
};
// @lc code=end

